Some devices that offer voice-communication capabilities are not configured to support the download and playback of recorded audio data. In addition, many devices that are able to receive and playback audio data, such as by receiving and playing audio data communicated as email attachments, may require a significant amount of time to download audio data over a data network. Thus, in many cases, it may be more effective to establish a voice connection to a messaging server that stores the audio recordings and to instruct the messaging server to play audio recordings from the user's account over the voice connection.
Many voicemail systems, however, play messages back to users in a serial fashion, starting with the voicemail message the user received first. Nonetheless, the user may not want to hear all of the messages that the user has received. Furthermore, the user may only have limited amount of time to check voicemail, such as while waiting for an airline flight, and may want to ensure that he or she hears a particular voicemail message received by the user.